home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 3: Developer Tools / Linux Cubed Series 3 - Developer Tools.iso / devel / lang / lisp / stk-3.0-b / stk-3 / blt-for-STk-3.0 / blt-1.9 / src / bltList.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-07-01  |  12.8 KB  |  493 lines
  1. /*
  2.  * bltList.c --
  3.  *
  4.  *    Generic linked list management routines.
  5.  *
  6.  * Copyright 1991-1994 by AT&T Bell Laboratories.
  7.  * Permission to use, copy, modify, and distribute this software
  8.  * and its documentation for any purpose and without fee is hereby
  9.  * granted, provided that the above copyright notice appear in all
  10.  * copies and that both that the copyright notice and warranty
  11.  * disclaimer appear in supporting documentation, and that the
  12.  * names of AT&T Bell Laboratories any of their entities not be used
  13.  * in advertising or publicity pertaining to distribution of the
  14.  * software without specific, written prior permission.
  15.  *
  16.  * AT&T disclaims all warranties with regard to this software, including
  17.  * all implied warranties of merchantability and fitness.  In no event
  18.  * shall AT&T be liable for any special, indirect or consequential
  19.  * damages or any damages whatsoever resulting from loss of use, data
  20.  * or profits, whether in an action of contract, negligence or other
  21.  * tortuous action, arising out of or in connection with the use or
  22.  * performance of this software.
  23.  *
  24.  */
  25.  
  26. #include "blt.h"
  27.  
  28. /*
  29.  *----------------------------------------------------------------------
  30.  *
  31.  * Blt_InitLinkedList --
  32.  *
  33.  *    Initialized a linked list.
  34.  *
  35.  * Results:
  36.  *    None.
  37.  *
  38.  *----------------------------------------------------------------------
  39.  */
  40. void
  41. Blt_InitLinkedList(listPtr, type)
  42.     Blt_LinkedList *listPtr;
  43.     int type;
  44. {
  45.  
  46.     listPtr->numEntries = 0;
  47.     listPtr->headPtr = listPtr->tailPtr = (Blt_ListEntry *)NULL;
  48.     listPtr->type = type;
  49. }
  50.  
  51. /*
  52.  *----------------------------------------------------------------------
  53.  *
  54.  * Blt_CreateLinkedList --
  55.  *
  56.  *    Creates a new linked list structure and initializes its pointers
  57.  *
  58.  * Results:
  59.  *    Returns a pointer to the newly created list structure.
  60.  *
  61.  *----------------------------------------------------------------------
  62.  */
  63. Blt_LinkedList *
  64. Blt_CreateLinkedList(type)
  65.     int type;
  66. {
  67.     Blt_LinkedList *listPtr;
  68.  
  69.     listPtr = (Blt_LinkedList *)malloc(sizeof(Blt_LinkedList));
  70.     if (listPtr != NULL) {
  71.     Blt_InitLinkedList(listPtr, type);
  72.     }
  73.     return (listPtr);
  74. }
  75.  
  76. /*
  77.  *----------------------------------------------------------------------
  78.  *
  79.  * Blt_CreateListEntry --
  80.  *
  81.  *    Creates a list entry holder.  This routine does not insert
  82.  *    the entry into the list, nor does it no attempt to maintain
  83.  *    consistency of the keys.  For example, more than one entry
  84.  *    may use the same key.
  85.  *
  86.  * Results:
  87.  *    The return value is the pointer to the newly created entry.
  88.  *
  89.  * Side Effects:
  90.  *    The key is not copied, only the Uid is kept.  It is assumed
  91.  *    this key will not change in the life of the entry.
  92.  *
  93.  *----------------------------------------------------------------------
  94.  */
  95. Blt_ListEntry *
  96. Blt_CreateListEntry(key)
  97.     char *key;            /* Unique key to reference object */
  98. {
  99.     register Blt_ListEntry *entryPtr;
  100.  
  101.     entryPtr = (Blt_ListEntry *)malloc(sizeof(Blt_ListEntry));
  102.     if (entryPtr != (Blt_ListEntry *)NULL) {
  103.     entryPtr->keyPtr = key;
  104.     entryPtr->clientData = (ClientData)NULL;
  105.     entryPtr->nextPtr = entryPtr->prevPtr = (Blt_ListEntry *)NULL;
  106.     }
  107.     return (entryPtr);
  108. }
  109.  
  110. /*
  111.  *----------------------------------------------------------------------
  112.  *
  113.  * Blt_DestroyListEntry --
  114.  *
  115.  *    Free the memory allocated for the entry.
  116.  *
  117.  * Results:
  118.  *    None.
  119.  *
  120.  *----------------------------------------------------------------------
  121.  */
  122. void
  123. Blt_DestroyListEntry(entryPtr)
  124.     Blt_ListEntry *entryPtr;
  125. {
  126.     free((char *)entryPtr);
  127. }
  128.  
  129. /*
  130.  *----------------------------------------------------------------------
  131.  *
  132.  * Blt_ClearList --
  133.  *
  134.  *    Removes all the entries from a list, removing pointers to the
  135.  *    objects and keys (not the objects or keys themselves).
  136.  *    The entry counter is reset to zero.
  137.  *
  138.  * Results:
  139.  *    None.
  140.  *
  141.  *----------------------------------------------------------------------
  142.  */
  143. void
  144. Blt_ClearList(listPtr)
  145.     Blt_LinkedList *listPtr;    /* List to clear */
  146. {
  147.     register Blt_ListEntry *oldPtr;
  148.     register Blt_ListEntry *entryPtr = listPtr->headPtr;
  149.  
  150.     while (entryPtr != (Blt_ListEntry *)NULL) {
  151.     oldPtr = entryPtr;
  152.     entryPtr = entryPtr->nextPtr;
  153.     Blt_DestroyListEntry(oldPtr);
  154.     }
  155.     Blt_InitLinkedList(listPtr, listPtr->type);
  156. }
  157.  
  158. /*
  159.  *----------------------------------------------------------------------
  160.  *
  161.  * Blt_DeleteLinkedList
  162.  *
  163.  *     Frees all list structures
  164.  *
  165.  * Results:
  166.  *    Returns a pointer to the newly created list structure.
  167.  *
  168.  *----------------------------------------------------------------------
  169.  */
  170. void
  171. Blt_DeleteLinkedList(listPtr)
  172.     Blt_LinkedList *listPtr;
  173. {
  174.     Blt_ClearList(listPtr);
  175.     free((char *)listPtr);
  176. }
  177.  
  178. /*
  179.  *----------------------------------------------------------------------
  180.  *
  181.  * Blt_LinkListAfter --
  182.  *
  183.  *    Inserts an entry following a given entry.
  184.  *
  185.  * Results:
  186.  *    None.
  187.  *
  188.  *----------------------------------------------------------------------
  189.  */
  190. void
  191. Blt_LinkListAfter(listPtr, entryPtr, afterPtr)
  192.     Blt_LinkedList *listPtr;
  193.     Blt_ListEntry *entryPtr;
  194.     Blt_ListEntry *afterPtr;
  195. {
  196.     /*
  197.      * If the list keys are strings, change the key to a Tk_Uid
  198.      */
  199.     if (listPtr->type == TCL_STRING_KEYS) {
  200.     entryPtr->keyPtr = Tk_GetUid(entryPtr->keyPtr);
  201.     }
  202.     if (listPtr->headPtr == (Blt_ListEntry *)NULL) {
  203.     listPtr->tailPtr = listPtr->headPtr = entryPtr;
  204.     } else {
  205.     if (afterPtr == (Blt_ListEntry *)NULL) {
  206.         afterPtr = listPtr->tailPtr;
  207.     }
  208.     entryPtr->nextPtr = afterPtr->nextPtr;
  209.     entryPtr->prevPtr = afterPtr;
  210.     if (afterPtr == listPtr->tailPtr) {
  211.         listPtr->tailPtr = entryPtr;
  212.     } else {
  213.         afterPtr->nextPtr->prevPtr = entryPtr;
  214.     }
  215.     afterPtr->nextPtr = entryPtr;
  216.     }
  217.     listPtr->numEntries++;
  218. }
  219.  
  220. /*
  221.  *----------------------------------------------------------------------
  222.  *
  223.  * Blt_LinkListBefore --
  224.  *
  225.  *    Inserts an entry preceding a given entry.
  226.  *
  227.  * Results:
  228.  *    None.
  229.  *
  230.  *----------------------------------------------------------------------
  231.  */
  232. void
  233. Blt_LinkListBefore(listPtr, entryPtr, beforePtr)
  234.     Blt_LinkedList *listPtr;    /* List to contain new entry */
  235.     Blt_ListEntry *entryPtr;    /* New entry to be inserted */
  236.     Blt_ListEntry *beforePtr;    /* Entry to link before */
  237. {
  238.     /*
  239.      * If the list keys are strings, change the key to a Tk_Uid
  240.      */
  241.     if (listPtr->type == TCL_STRING_KEYS) {
  242.     entryPtr->keyPtr = Tk_GetUid(entryPtr->keyPtr);
  243.     }
  244.     if (listPtr->headPtr == (Blt_ListEntry *)NULL) {
  245.     listPtr->tailPtr = listPtr->headPtr = entryPtr;
  246.     } else {
  247.     if (beforePtr == (Blt_ListEntry *)NULL) {
  248.         beforePtr = listPtr->headPtr;
  249.     }
  250.     entryPtr->prevPtr = beforePtr->prevPtr;
  251.     entryPtr->nextPtr = beforePtr;
  252.     if (beforePtr == listPtr->headPtr) {
  253.         listPtr->headPtr = entryPtr;
  254.     } else {
  255.         beforePtr->prevPtr->nextPtr = entryPtr;
  256.     }
  257.     beforePtr->prevPtr = entryPtr;
  258.     }
  259.     listPtr->numEntries++;
  260. }
  261.  
  262. /*
  263.  *----------------------------------------------------------------------
  264.  *
  265.  * Blt_UnlinkListEntry --
  266.  *
  267.  *    Unlinks an entry from the given list. The entry itself is
  268.  *    not deallocated, but only removed from the list.
  269.  *
  270.  * Results:
  271.  *    None.
  272.  *
  273.  *----------------------------------------------------------------------
  274.  */
  275. void
  276. Blt_UnlinkListEntry(listPtr, entryPtr)
  277.     Blt_LinkedList *listPtr;
  278.     Blt_ListEntry *entryPtr;
  279. {
  280.     if (listPtr->headPtr == entryPtr) {
  281.     listPtr->headPtr = entryPtr->nextPtr;
  282.     }
  283.     if (listPtr->tailPtr == entryPtr) {
  284.     listPtr->tailPtr = entryPtr->prevPtr;
  285.     }
  286.     if (entryPtr->nextPtr != NULL) {
  287.     entryPtr->nextPtr->prevPtr = entryPtr->prevPtr;
  288.     }
  289.     if (entryPtr->prevPtr != NULL) {
  290.     entryPtr->prevPtr->nextPtr = entryPtr->nextPtr;
  291.     }
  292.     listPtr->numEntries--;
  293. }
  294.  
  295. #ifdef notdef
  296. /*
  297.  *----------------------------------------------------------------------
  298.  *
  299.  * Blt_SetListValue --
  300.  *
  301.  *    Sets the entry data pointer to the given value.
  302.  *
  303.  * Results:
  304.  *    None.
  305.  *
  306.  * Side Effects:
  307.  *    The data is not copied, only the pointer is kept.  It is assumed
  308.  *    this data will remain valid as long as the entry.
  309.  *
  310.  *----------------------------------------------------------------------
  311.  */
  312. void
  313. Blt_SetListValue(entryPtr, clientData)
  314.     Blt_ListEntry *entryPtr;    /* Pointer to the entry */
  315.     ClientData clientData;    /* Data attached to key */
  316. {
  317.     entryPtr->clientData = clientData;
  318. }
  319.  
  320. #endif
  321. /*
  322.  *----------------------------------------------------------------------
  323.  *
  324.  * Blt_ListIndex --
  325.  *
  326.  *    Find the position of an entry in the list.
  327.  *
  328.  * Results:
  329.  *    Returns the index to the entry.  If no entry matching
  330.  *    the key given is found, then -1 is returned.
  331.  *
  332.  *----------------------------------------------------------------------
  333.  */
  334. int
  335. Blt_ListIndex(listPtr, searchPtr)
  336.     Blt_LinkedList *listPtr;    /* List to search */
  337.     Blt_ListEntry *searchPtr;    /* Entry to match */
  338. {
  339.     register int count = 0;
  340.     register Blt_ListEntry *entryPtr;    /* Entry to match */
  341.  
  342.     for (entryPtr = listPtr->headPtr; entryPtr != NULL;
  343.     entryPtr = entryPtr->nextPtr) {
  344.     if (searchPtr == entryPtr)
  345.         return (count);
  346.     count++;
  347.     }
  348.     return (-1);
  349. }
  350.  
  351. /*
  352.  *----------------------------------------------------------------------
  353.  *
  354.  * Blt_FindListEntry --
  355.  *
  356.  *    Find the first entry matching the key given.
  357.  *
  358.  * Results:
  359.  *    Returns the pointer to the entry.  If no entry matching
  360.  *    the key given is found, then NULL is returned.
  361.  *
  362.  *----------------------------------------------------------------------
  363.  */
  364. Blt_ListEntry *
  365. Blt_FindListEntry(listPtr, searchKey)
  366.     Blt_LinkedList *listPtr;    /* List to search */
  367.     char *searchKey;        /* Key to match */
  368. {
  369.     register Blt_ListEntry *entryPtr;
  370.     Tk_Uid newPtr;
  371.  
  372.     newPtr = searchKey;
  373.     if (listPtr->type == TCL_STRING_KEYS) {
  374.     newPtr = Tk_GetUid(searchKey);
  375.     }
  376.     for (entryPtr = listPtr->headPtr; entryPtr != NULL;
  377.     entryPtr = entryPtr->nextPtr) {
  378.     if (newPtr == entryPtr->keyPtr)
  379.         return (entryPtr);
  380.     }
  381.     return (Blt_ListEntry *) NULL;
  382. }
  383.  
  384. #ifdef notdef
  385. /*
  386.  *----------------------------------------------------------------------
  387.  *
  388.  * Blt_FirstListEntry --
  389.  *
  390.  *    Find the first entry in the list and return its pointer.
  391.  *    In addition, update the given search pointer.
  392.  *
  393.  * Results:
  394.  *    Returns a pointer to the first entry in the list. If the
  395.  *      list is empty, NULL is returned.  The search pointer (used in
  396.  *    subsequent searches) is set to the appropriate value.
  397.  *
  398.  *----------------------------------------------------------------------
  399.  */
  400. Blt_ListEntry *
  401. Blt_FirstListEntry(listPtr, entryPtrPtr)
  402.     Blt_LinkedList *listPtr;    /* The list we are searching */
  403.     Blt_ListEntry **entryPtrPtr;/* Search pointer to set */
  404. {
  405.     if (listPtr == (Blt_LinkedList *)NULL)
  406.     return (Blt_ListEntry *) NULL;
  407.  
  408.     if (listPtr->headPtr == (Blt_ListEntry *)NULL)
  409.     return (Blt_ListEntry *) NULL;
  410.  
  411.     if (entryPtrPtr != (Blt_ListEntry **)NULL) {
  412.     *entryPtrPtr = listPtr->headPtr;
  413.     }
  414.     return (listPtr->headPtr);
  415. }
  416.  
  417. /*
  418.  *----------------------------------------------------------------------
  419.  *
  420.  * Blt_ListLastEntry --
  421.  *
  422.  *    Find the last entry in the list using the given entry as
  423.  *    a cursor to the last entry and return its pointer.
  424.  *    In addition, the cursor position is updated.
  425.  *
  426.  * Results:
  427.  *    A pointer to the last object in the list is returned. If the
  428.  *      list is at end, NULL is returned.  The search pointer (used in
  429.  *    subsequent searches) is set to the appropriate value.
  430.  *
  431.  *----------------------------------------------------------------------
  432.  */
  433. Blt_ListEntry *
  434. Blt_ListLastEntry(entryPtrPtr)
  435.     Blt_ListEntry **entryPtrPtr;/* Search pointer of current position */
  436. {
  437.     if ((entryPtrPtr == (Blt_ListEntry **)NULL) ||
  438.     (*entryPtrPtr == (Blt_ListEntry *)NULL)) {
  439.     return (Blt_ListEntry *) NULL;
  440.     }
  441.     *entryPtrPtr = (*entryPtrPtr)->prevPtr;
  442.     return (*entryPtrPtr);
  443. }
  444.  
  445. /*
  446.  *----------------------------------------------------------------------
  447.  *
  448.  * Blt_NextListEntry --
  449.  *
  450.  *    Find the next entry in the list using the given search pointer
  451.  *    as the current location and return its pointer.
  452.  *    In addition, update the given search pointer.
  453.  *
  454.  * Results:
  455.  *    A pointer to the next object in the list is returned. If the
  456.  *      list is at end, NULL is returned.  The search pointer (used in
  457.  *    subsequent searches) is set to the appropriate value.
  458.  *
  459.  *----------------------------------------------------------------------
  460.  */
  461. Blt_ListEntry *
  462. Blt_NextListEntry(entryPtrPtr)
  463.     Blt_ListEntry **entryPtrPtr;/* Search pointer indicates current position */
  464. {
  465.     if ((entryPtrPtr == NULL) || (*entryPtrPtr == NULL)) {
  466.     return (Blt_ListEntry *) NULL;
  467.     }
  468.     *entryPtrPtr = (*entryPtrPtr)->nextPtr;
  469.     return (*entryPtrPtr);
  470. }
  471.  
  472. #endif
  473. /*
  474.  *----------------------------------------------------------------------
  475.  *
  476.  * Blt_DeleteListEntry --
  477.  *
  478.  *    Find the entry and free the memory allocated for the entry.
  479.  *
  480.  * Results:
  481.  *    None.
  482.  *
  483.  *----------------------------------------------------------------------
  484.  */
  485. void
  486. Blt_DeleteListEntry(listPtr, entryPtr)
  487.     Blt_LinkedList *listPtr;
  488.     Blt_ListEntry *entryPtr;
  489. {
  490.     Blt_UnlinkListEntry(listPtr, entryPtr);
  491.     Blt_DestroyListEntry(entryPtr);
  492. }
  493.